#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 5
// 线性表及其实现
/*
线性表是由同类数据元素构成有序序列的线性结构
-->表中元素个数称为线性表的长度
-->线性表没有元素时，称为空表
-->表起始位置称表头，表结束位置称表尾
*/
// 线性表的顺序存储实现
typedef struct LNode *List;
struct LNode
{
    int Data[MAXSIZE];
    int Last; // 标注最后一个元素的位置
};

// 建立空的顺序表
List MakeEmpty()
{
    List PtrL;
    PtrL = (List)malloc(sizeof(struct LNode));
    PtrL->Last = -1;
    return PtrL;
}

// 查找
int Find(int x, List PtrL)
{
    int i = 0;
    while (i <= PtrL->Last && PtrL->Data[i] != x)
        i++;
    if (i > PtrL->Last)
        return -1; // 如果没找到就返回-1
    else
        return i;
}


//插入
//在第i个位置上插入一个值为X的新元素
void Insert(int x,int i,List PtrL)
{
    int j;
    if(PtrL->Last == MAXSIZE - 1)//表空间已满，不能再插入
    {
        printf("表满");
        return;
    }
    if(i < 1 || i > PtrL->Last + 2)//判断插入位置的合法性
    {
        printf("位置不合法");
        return;
    }
    for (j = PtrL->Last; j >= i - 1; j--)
    {
        PtrL->Data[j + 1] = PtrL->Data[j];
    }
    PtrL->Data[i - 1] = x;
    PtrL->Last++;
    return;
}





//删除
//删除表上的第i个位置的元素
void Delete(int i,List PtrL)
{
    if(i < 1 || i > PtrL->Last+1)
    {
        printf("插入位置不合法");
        return;
    }
    for (int j = i; j < PtrL->Last;j++)
        PtrL->Data[j] = PtrL->Data[j + 1];
    PtrL->Last--;
    return;
}




//上面的链式表我们通过数组的形式来存储，同样地，我们可以通过链表的方式来存储
//线性表的链式存储实现
struct LNode_Linear{
    int Data;
    struct LNode_Linear* Next;
};



//链表遍历法求表长
int Length(struct LNode_Linear* PtrL)
{
    struct LNode_Linear *p = PtrL;
    int counter = 0;
    while(p)
    {
        p = p->Next;
        counter++;
    }
    return counter;
}



//查找。
//（1）按序号查找
int FindKth(int k,struct LNode_Linear* PtrL)
{
    struct LNode_Linear *p = PtrL;
    /* for (int i = k; i > 1;i--)
    {
        p = p->Next;
    }
    return p->Data; */   //这个方法有一个问题，就是如果输入的k太大了，找到链表末尾也没找到该怎么办？
    int i = 1;
    while(p != NULL && i < k)
    {
        p = p->Next;
        i++;
    }
    if(i == k)
        return p->Data;
    else
        return -1;//如果是链表内有-1该怎么办呢？我们可以将返回值改为指针，若超出范围就范围NULL。
}

//（2）按值查找
struct LNode_Linear *Find(struct LNode_Linear *PtrL,int x)
{
    struct LNode_Linear *p = PtrL;
    while(p)
    {
        if(p->Data == x)
            break;
        p = p->Next;
    }
        return p;
}



//插入
//在第i-1个节点后面插入一个值为x的新结点
struct LNode_Linear* Insert_Linear(struct LNode_Linear* PtrL,int i,int x)
{
    struct LNode_Linear *q = (struct LNode_Linear *)malloc(sizeof(struct LNode_Linear));
    q->Data = x, q->Next = NULL;//申请内存，封装结点
    struct LNode_Linear *p = PtrL;
    if(i == 1)//插入位置在表头(0这个位置在链表上是不存在的)
    {
        q->Next = PtrL;
        return q;
    }
    //寻找第i-1个结点,这一段可以接入Find函数
    int counter = 0;
    while(p != NULL && counter < i - 2)
    {
        p = p->Next;
        counter++;
    }
    if(p == NULL)
    {
        printf("输入i值超出范围");
        free(q);//先释放内存
        return PtrL;
    }
    else//在第i-1个结点后面插入
    {
        q->Next = p->Next;
        p->Next = q;
        return PtrL;
    }
}


//删除结点
//删除链表的第i个位置上的结点
 struct LNode_Linear* Delete(int i,struct LNode_Linear* PtrL)
 {
     struct LNode_Linear *p, *s;
     // 首先考虑要删除的是头节点
     if (i == 1)
     {
         s = PtrL;
         // 若链表本身为空，则直接返回NULL
         if (PtrL == NULL)
             return NULL;
         else
        {
            PtrL = PtrL->Next;
            free(s);
        }
    }
    //其次考虑其他情况
    //先找到第i-1个结点
    int counter = 0;
    while (p != NULL && counter < i - 2)
    {
        p = p->Next;
        counter++;
    }
    if(p == NULL)//删除位置不对
    {
        printf("删除位置不对");
        return NULL;
    }
    else
    {
        s = p->Next;
        p->Next = s->Next;
        free(s);
        return PtrL;
    }
 }












